package com.eagle.zstudy.suanfa;

public class Kuaipai {

	public static void main(String[] args) {
		kuaiPai();
	}
	
	private static void quickSort(int[] arr, int start, int end ){
		if( start >= end ){
			return ;
		}
		int s = start;
		int e = end ;
		int flag = arr[start];
		while( s < e ){
			//从后往前找<flag的数，并填充arr[s]
			while( s < e && arr[e] > flag){
				e--;
			}
			if( s < e ){
				arr[s] = arr[e];
				s++ ;
			}
			//从前往后找>=falg的数，并填充arr[e]
			while( s < e && arr[s] <= flag){
				s++;
			}
			if( s < e ){
				arr[e] = arr[s];
				e--;
			}
		}
		arr[s] = flag ;
		printIntArr( arr );
		//递归
		quickSort(arr, start, s-1);
		quickSort(arr, s+1, end);
	}
	
	private static void kuaiPai(){
		int[] arr = new int[20];
		for (int i = 0; i < 20 ; i++) {
			arr[i] = (int) (Math.random()*100); 
		}
		printIntArr( arr );
		quickSort(arr, 0, arr.length-1);
	}
	
	private static void printIntArr( int[] arr ){
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i]+",");
			if( i == arr.length-1 ){
				System.out.print(arr[i]+"\n");
			}
		}
	}
	
}
